import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/8 22:32
 * @description 动态规划2 优化， 利用滚动数组，将空间优化为 O(n)
 */
public class Solution3 {
    public static void main(String[] args) {

    }
    public int minimumTotal(List<List<Integer>> tri) {
        int n = tri.size();
        int ans = Integer.MAX_VALUE;
        // 使用两个长度为n的一维数组进行转移，将i根据奇偶性映射到一个数组，那么i-1就映射到了另一个数组，这样就使用使用两个数组实现状态转换。
        int[][] f = new int[2][n];
        f[0][0] = tri.get(0).get(0);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i + 1; j++) {
                int val = tri.get(i).get(j);
                f[i & 1][j] = Integer.MAX_VALUE;
                if (j != 0) f[i & 1][j] = Math.min(f[i & 1][j], f[(i - 1) & 1][j - 1] + val);
                if (j != i) f[i & 1][j] = Math.min(f[i & 1][j], f[(i - 1) & 1][j] + val);
            }
        }
        for (int i = 0; i < n; i++) ans = Math.min(ans, f[(n - 1) & 1][i]);
        return ans;
    }
}
